int a[N];
bool vis[N];

void dfs(int dep){
	if (dep == n+1) {
		for (int i=1;i<=n;i++) {
			cout << a[i] << ' ';
		}
		cout << '\n';
		return;
	}
	
	for (int i=1;i<=n;i++) {
		// 排除不合法的路径
		if (vis[i]) continue;
		
		// 修改状态
		vis[i] = true;
		a[dep] = i;
		
		// 下一层
		dfs(dep+1);
		
		// 恢复现场
		vis[i] = false;		
	}
}
